googologywikiaorg-20200223-history
Forum:The largest computable number spec
Hi! I'm not a regular contributor to this Wiki and didn't think it appropriate to edit directly. My contribution to XKCD's "My number is bigger" thread was acknowledged by some other posters as having probably won the thread; the thread rules specified that number specifications had to be computable (no Busy Beavers or beyond) and could not make use of a previously defined number. I also gave an argument for why my number was the largest kind of computable specification for a finite integer that could be constructed using current mathematical technology, at least until someone invents more powerful large cardinal axioms or a different approach. http://forums.xkcd.com/viewtopic.php?p=3254229#p3254229 Throwing it here so somebody can put it on the Wiki if they consider that interesting. -- Eliezer Yudkowsky :Hey Eliezer, thanks for your contribution! :It's clear that one can vary initial value of P, number of repetitions or used function (you used 2^^P), but idea stays the same. :Argument you give on why this number is probably the biggest computable works, expect for a minor/major difficulty - it requires theory of ZFC+I0 to be sound, so that if it proves that a machine halts, then that machine indeed halts. :As you probably know, soundness is quite strong property, and thus we don't know if ZFC+I0 is sound (for the matter of fact, I don't think even ZF was proven sound). :Also, it might be a case that Morse-Kelley theory analogue of this will be larger, as MK can prove consistence of ZFC along with few of it extensions. LittlePeng9 (talk) 21:33, May 23, 2014 (UTC) :What about Reinhardt cardinals? I'm not sure about what inconsistency with ZFC implies, however. you're.so. 22:26, May 23, 2014 (UTC) ::Let's assume contradiction is provable in theory T with a reasonable length of proof (say, 10^^^^^10, it is the case for ZFC+Reinhardt cardinal exists). Let M be a trivial non-halting machine. Because contradiction can be proven reasonably fast, so can be any statement, including "M halts". But this means T is unsound, and proves false statement. ::Let machine P be as in XKCD post above, except it works with T. After wirking for a bit, P will find a proof that M halts and will try to find halting time of it. But in reality M does not halt, so P will work forever, not computing any number. LittlePeng9 (talk) 04:32, May 24, 2014 (UTC) ::However, if Reinhardt cardinal turns out to be consistent with ZF alone, we will get a system much stronger than Eliezer's, and number much larger than his. LittlePeng9 (talk) 04:35, May 24, 2014 (UTC) :::So in other words, we can't reliably take advantage of Reinhardt cardinals until we've shown that ZF + "there exists a Reinhardt cardinal" is consistent. But then again, the same uncertainty applies to ZFC+I0, ZFC + "there is a Mahlo cardinal", ZFC + "there is an inaccessible cardinal," ZFC, ZF, and even Peano arithmetic if my sources are correct. Granted, it's more reasonable to doubt the consistency of ZFC plus some large cardinal axiom than ZF, but that's just an intuitive judgement. Objectively speaking, it makes just as much sense to doubt the consistency of ZF + "there exists a Reinhardt cardinal" as the totality of the Goodstein function. Right? you're.so. 16:12, May 24, 2014 (UTC) ::::Well, I disagree about PA mention and Goodstein function analogy. We can argue that PA is consistent by using well-foundedness of \(\varepsilon_0\), which is quite reasonable statement. If you don't want to take it for granted, then you probably have something of a formalist in you. In that case, to prove that induction up to \(\varepsilon_0\) makes sense, we have to use some stronger theory. But we don't know if it's sound/consistent, and to prove that we need an even stronger system, and so on (giving us so called "consistency hierarchy"). But that goes for everything - if we want to believe \(n^2\geq n\), which is a nontrivial theorem of PA, we have to assume its consistence. And we need to start somewhere - we need a system for which we take for granted that it's consistent. I believe second order arithmetic is good for this purpose, as it's a simple system which seems really reasonable. On the other hand, to believe consistency of, say, ZFC, we need a system a lot stronger than that, like Morse-Kelley set theory. But these systems are so vast and complex one can really doubt their consistency. ::::To sum up, in my opinion, PA consistency and Goodstein sequence totality follow from a very reasonable statement of arithmetic, but it's on far lower level than ZFC and large cardinal axioms, for which there is no reasonable statement which proves their consistency. So analogy you give is pretty much meaningless, although to some extent you are right. LittlePeng9 (talk) 16:50, May 24, 2014 (UTC) :::::I stand corrected. I was under the impression that the consistency of PA is a mere work in progress; I was unaware that there's a 'turtles-all-the-way-down' dilemma when it comes to axiomatic theories. you're.so. 20:28, May 24, 2014 (UTC)